package com.lft.ten_commonly_used_algorithms01.binary_search;

/**
 * 二分查找算法（非递归实现）
 */
public class BinarySearchNoRecursion {
	public static void main(String[] args) {
		// 前提条件，有序号数组。
		int[] array = {1, 3, 8, 10, 11, 67, 100};
		int index = binarySearchNoRecursion(array, 100);
		System.out.println(index);
	}
	
	/**
	 * 二分查找算法
	 * @param array  待查找的有序（升序）数组
	 * @param target 要查找的数。
	 * @return 返回对应下标。未找到返回 -1
	 */
	public static int binarySearchNoRecursion(int[] array, int target) {
		int left = 0;
		int right = array.length - 1;
		int mid;
		// 继续查找
		while (left <= right) {
			// 中间索引
			mid = (left + right) / 2;
			// 当前索引下的数组中的值正好等于target
			if (array[mid] == target) {
				// 返回 mid 索引
				return mid;
			}
			// 目标值比 mid 索引中的值小。
			else if (array[mid] > target) {
				// 往左查找。将right 放到 原 mid 前一位置再循环遍历。
				right = mid - 1;
			}
			// 目标值比 mid 索引中的值大。
			else {
				// 往右查找。将left 放到 原 mid 后一位置再循环遍历。
				left = mid + 1;
			}
		}
		return -1;
	}
}
